package tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 110. 平衡二叉树
 * 二叉树高度用后序遍历，从下到上
 * 二叉树深度用前序遍历，从上到下
 *
 * @author Api
 * @date 2023/10/22 15:51
 */
public class Code110_BalancedBinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {

        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isBalanced(TreeNode root) {
        int height = getHeight(root);
        return height != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        // 右
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 中
        int result = 0;
        if (Math.abs(rightHeight - leftHeight) > 1) {
            result = -1;
        } else {
            result = 1 + Math.max(rightHeight, leftHeight);
        }
        return result;
    }
    // 层序遍历，求结点的高度
    public int getHeight1(TreeNode root){
        if (root == null){
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while(!deque.isEmpty()){
            int size = deque.size();
            depth++;
            while(size-- > 0){
                TreeNode node = deque.poll();
                if (node.left != null){
                    deque.add(node.left);
                }
                if (node.right != null){
                    deque.add(node.right);
                }
            }
        }
        return depth;
    }
}
